// 插入排序
const arr = [2, 4, 7, 9, 6, 4, 1, 5, 3, 2];
// i = 1  [2, 4, 7, 9, 6, 4, 1, 5, 3, 2]
// i = 2  [2, 4, 7, 9, 6, 4, 1, 5, 3, 2]
// i = 3  [2, 4, 7, 9, 6, 4, 1, 5, 3, 2]
// i = 4  [2, 4, 6, 7, 9, 4, 1, 5, 3, 2]

function insertSort(arr) {
  let prevIndex, current;

  for(let i = 1; i < arr.length; i++) {
    // console.log(i)
    // [2, 4, 6, 7, 9, 4, 1, 5, 3, 2]
    // 循环的位置
    prevIndex = i - 1;  // 3
    // // 记录当前的值
    current = arr[i]    // 6

    while(prevIndex >= 0 && current < arr[prevIndex]) {
      arr[prevIndex + 1] = arr[prevIndex] 
      prevIndex--
    }
    console.log(prevIndex + 1)
    arr[prevIndex + 1] = current
  }
  return arr
}

const result = insertSort(arr);
console.log(result)

